#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

struct Stone {
    int s, e, l;
    bool operator< (const Stone &W) const{
        return s * W.l < W.s * l;
    }
}stone[N];

int f[N];

int main() {
    int T;
    cin >> T;
    
    int cnt = 1;
    while (T -- ) {
        
        int n, m = 0;
        cin >> n;
        
        for (int i = 0; i < n; ++ i) {
            int s, e, l;
            cin >> s >> e >> l;
            stone[i] = {s, e, l};
        }
        
        sort(stone, stone + n);
        
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        
        for (int i = 0; i < n; ++ i) {
            int s = stone[i].s, e = stone[i].e, l = stone[i].l;
            m += s;
            for (int j = m; j >= s; -- j)
                f[j] = max(f[j], f[j - s] + e - (j - s) * l);
        }
        
        int res = 0;
        for (int j = 0; j <= m; ++ j) res = max(res, f[j]);
        
        printf("Case #%d: %d\n", cnt ++, res);
    }
    
    return 0;
}